package com.algorithm2;

import java.util.Arrays;

public class QuickSort2 {

    public static void main(String[] args){
        int[] array = new int[]{0,8, 9, 3,10, 2, 4, 5, 6, 7, 1};
        quickSort(array,array.length);
        System.out.println("排序完数据:"+ Arrays.toString(array));
    }
    public static void quickSort(int[] array,int n){
        quickSortSub(array,0,n-1);

    }
    public static int partion(int[] array,int p,int r){
        int pivot = array[r];
        int i = p;//i的前面是排好序的，i是代表需要交换的对象，一般比pivot大
        for(int j=p;j<r;j++){
            if(array[j]<pivot){
                swap(array,i,j);
                i++;
            }
        }
        swap(array,i,r);
        System.out.println("分区后的array:"+Arrays.toString(array));
        return i;
    }

    public static void swap(int[] array,int i,int j){
        int temp =array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void quickSortSub(int[] array,int p,int r){
        if( p>=r )
            return;
        int pivot = partion(array,p,r);//获取分区点
        quickSortSub(array,p,pivot-1);
        quickSortSub(array,pivot+1,r);
    }
}
